<html>
<head><meta charset="utf-8"><title>Is CopyPropagation working correctly? · t-compiler/wg-mir-opt · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/index.html">t-compiler/wg-mir-opt</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html">Is CopyPropagation working correctly?</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="198705028"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/198705028" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#198705028">(May 25 2020 at 22:02)</a>:</h4>
<p>These mir-opt tests all show empty diffs:</p>
<ul>
<li><a href="https://github.com/rust-lang/rust/tree/master/src/test/mir-opt/copy_propagation_arg">https://github.com/rust-lang/rust/tree/master/src/test/mir-opt/copy_propagation_arg</a></li>
</ul>
<p>This one seems okay:</p>
<ul>
<li><a href="https://github.com/rust-lang/rust/blob/master/src/test/mir-opt/copy_propagation/rustc.test.CopyPropagation.diff">https://github.com/rust-lang/rust/blob/master/src/test/mir-opt/copy_propagation/rustc.test.CopyPropagation.diff</a></li>
</ul>



<a name="198705136"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/198705136" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#198705136">(May 25 2020 at 22:04)</a>:</h4>
<p>My destination propagation pass will also make the latter a no-op. I guess we can remove the copy-prop pass entirely, it's slow and hasn't seen any significant improvements in years.</p>



<a name="198710217"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/198710217" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#198710217">(May 26 2020 at 00:10)</a>:</h4>
<p>Ohh, that's super cool <span class="user-mention" data-user-id="211727">@Jonas Schievink</span></p>



<a name="198710270"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/198710270" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#198710270">(May 26 2020 at 00:10)</a>:</h4>
<p>So I'm guessing that copy-prop and destination prop are the same optimization in this context?</p>



<a name="198710274"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/198710274" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#198710274">(May 26 2020 at 00:11)</a>:</h4>
<p>Only they are different names</p>



<a name="198710277"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/198710277" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#198710277">(May 26 2020 at 00:11)</a>:</h4>
<p>Like copy-prop is the old one, and dest-prop is the new one you're making?</p>



<a name="198710280"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/198710280" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#198710280">(May 26 2020 at 00:11)</a>:</h4>
<p>Or is destination prop a generalization of copy prop?</p>



<a name="198745520"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/198745520" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#198745520">(May 26 2020 at 10:54)</a>:</h4>
<p>My understanding is that copy propagation is a general concept, not a specific optimization. The old copy propagation pass is very simplistic and only handles a couple of cases, so it's possible that my pass can optimize strictly more code, although I haven't checked this. Destination propagation is a somewhat more specific term that includes the way copies are propagated (by moving the <code>x</code> destination of some <code>x = y;</code> copy backwards to where <code>y</code> used to be).</p>



<a name="198792587"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/198792587" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#198792587">(May 26 2020 at 17:09)</a>:</h4>
<p>Ahh, I see :)</p>



<a name="210583908"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/210583908" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#210583908">(Sep 18 2020 at 23:03)</a>:</h4>
<p>We now have a bit more data on this: <a href="https://github.com/rust-lang/rust/pull/76569#issuecomment-691162316">https://github.com/rust-lang/rust/pull/76569#issuecomment-691162316</a></p>
<p>It looks like dest prop performs roughly the same number of propagations as the old copy prop pass, but they are different subsets, so copy prop is still beneficial.</p>
<p>This makes sense, since copy prop does forward propagation, while dest prop propagates backwards. Some propagations only work in one direction.</p>



<a name="210584428"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/210584428" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#210584428">(Sep 18 2020 at 23:10)</a>:</h4>
<p>(I'm still going to go ahead with the removal – turns out copy prop has been unsound for a while <a href="https://github.com/rust-lang/rust/issues/76740">#76740</a>, and we should be able to reuse a bunch of the logic from dest prop in a future forwards propagation pass)</p>



<a name="210586745"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/210586745" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#210586745">(Sep 18 2020 at 23:57)</a>:</h4>
<p>if you want best efficiency, you want to combine and interleave forward and back propagation together with const propagation in a single pass that does all of these things until it reaches a fixpoint.</p>



<a name="210586793"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/210586793" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#210586793">(Sep 18 2020 at 23:58)</a>:</h4>
<p>there are examples of instruction sequences where any one of the three missing would miss an optimisation.</p>



<a name="210586807"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/210586807" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#210586807">(Sep 18 2020 at 23:59)</a>:</h4>
<p>That said, we still haven’t an alias analysis in rustc, so I have no idea how y'all are planning to make any sound propagation optimisation.</p>



<a name="210586905"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/210586905" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#210586905">(Sep 19 2020 at 00:00)</a>:</h4>
<p>Sounds reasonable</p>



<a name="210586921"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/210586921" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#210586921">(Sep 19 2020 at 00:00)</a>:</h4>
<p><span class="user-mention silent" data-user-id="123586">nagisa</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F/near/210586807">said</a>:</p>
<blockquote>
<p>That said, we still haven’t an alias analysis in rustc, so I have no idea how y'all are planning to make any sound propagation optimisation.</p>
</blockquote>
<p>Currently by ignoring locals whose addresses are taken entirely</p>



<a name="210587040"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/210587040" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nagisa <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#210587040">(Sep 19 2020 at 00:02)</a>:</h4>
<p>hm, I have a feeling that this was not sufficient last time I looked at implementing propagation many many years ago, but I don’t remember if that was actually true anymore.</p>



<a name="210587137"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/210587137" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#210587137">(Sep 19 2020 at 00:04)</a>:</h4>
<p>There's lots of code in the dest prop pass to track conflicts between locals, if that's what you mean</p>



<a name="210587243"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Is%20CopyPropagation%20working%20correctly%3F/near/210587243" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Is.20CopyPropagation.20working.20correctly.3F.html#210587243">(Sep 19 2020 at 00:06)</a>:</h4>
<p>It also bails out when a candidate place contains indirection in general, etc.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>